/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project2;

/**
 *generic Tree class
 * @author deylo
 */
public class Tree<T extends Comparable<T>> {

    private GenTreeNode root;

    /**
     * Default contructor
     */
    public Tree() {
        root = null;
    }

    /**
     * constructor takes one type param
     * @param data: data to be stored
     */
    public void InsertNode(T data) {
        if (root == null) {
            root = new GenTreeNode(data, root);
        } else {
            root.insert(data, root);
        }
    }

    /**
     * preorder traversal
     */
    public void preorderTraversal() {
        preorderHelper(root);
    }

    /**
     * preorder helper
     * @param node: recursive node
     */
    private void preorderHelper(GenTreeNode node) {
        if (node == null) {
            return;
        }

        System.out.println(node.data);
        preorderHelper(node.leftNode);
        preorderHelper(node.rightNode);
    }

    /**
     * inorder traversal
     */
    public void inorderTraversal() {
        inorderHelper(root);
    }

    /**
     * inodrer helper
     * @param node: recursive node
     */
    private void inorderHelper(GenTreeNode node) {
        if (node == null) {
            return;
        }
        inorderHelper(node.leftNode);
        System.out.println(node.data);
        inorderHelper(node.rightNode);
    }

    /**
     * postoreder traversal
     */
    public void postorderTraversal() {
        postorderHelper(root);
    }

    /**
     * postorder helper
     * @param node: recursive node
     */
    private void postorderHelper(GenTreeNode node) {
        if (node == null) {
            return;
        }
        postorderHelper(node.leftNode);
        postorderHelper(node.rightNode);
        System.out.println(node.data);
    }

    /**
     * returns the size
     * @return: size
     */
    public int size() {
        if (root == null) {
            return 0;
        }
        return sizeHelper(root);
    }

    /**
     * recursive method to find size
     * @param node: recursive node
     * @return: size returned
     */
    private int sizeHelper(GenTreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + sizeHelper(node.leftNode) + sizeHelper(node.rightNode);
    }

    /**
     * Override toString method
     * @return: return string
     */
    public String toString() {
        if (root == null) {
            return new String("Tree is empty.");
        }
        return stringHelper(root);
    }

    /**
     * recursive method to print all string
     * @param node: recursive node
     * @return: string
     */
    private String stringHelper(GenTreeNode node) {
        if (node == null) {
            return null;
        }

        String s1 = stringHelper(node.leftNode);
        String s2 = node.data.toString();
        String s3 = stringHelper(node.rightNode);

        StringBuilder s = new StringBuilder();
        if (s1 != null) {
            s.append(s1 + " ");
        }
        s.append(s2);
        if (s3 != null) {
            s.append(" " + s3);
        }
        return s.toString();
    }

    /**
     * reversse traversal
     */
    public void reverseorderTraversal() {
        reverseorderHelper(root);
    }

    /**
     * recusrive reverseorder helper method
     * @param node: recursive node
     */
    private void reverseorderHelper(GenTreeNode node) {
        if (node == null) {
            return;
        }
        reverseorderHelper(node.rightNode);
        System.out.println(node.data);
        reverseorderHelper(node.leftNode);
    }

    /**
     * how deep the rabit whole is, path to deepest leaf
     * @return: depth in int.
     */
    public int depth() {
        return depthHelper(root);
    }
/**
 * Depth Helper, recursivelly finds the deepest path then keeps track of it
 * @param node: recursive node
 * @return: returns the path as int
 */
    private int depthHelper(GenTreeNode node) {
        int _rightDepth = 0;
        int _leftDepth = 0;

        if (node == null) {
            return 0;
        }
        _leftDepth = depthHelper(node.leftNode) + 1;
        _rightDepth = depthHelper(node.rightNode) + 1;

        if (_leftDepth > _rightDepth) {
            return _leftDepth;
        } else {
            return _rightDepth;
        }
    }

    /**
     * Return true is number in this case Data is found in tree
     * @param data: data to be found
     * @return: true of false based on search find.
     */
    public boolean numberInTree(T data) {
        return numberInTreeHelper(root, data);
    }

    /**
     * Helper to finder numberInTree
     * @param node: recursive node
     * @param data: data to find
     * @return true of false based on search find.
     */
    private boolean numberInTreeHelper(GenTreeNode node, T data) {
        if (node == null) {
            return false;
        }

        if (node.data.compareTo(data) == 0) {
            return true;
        } else if (node.data.compareTo(data) == -1) {//T data in is greater goes right
            return numberInTreeHelper(node.rightNode, data);
        } else {
            return numberInTreeHelper(node.leftNode, data);
        }
    }

    /**
     * find the maxNode in a Tree with max data value
     * @return: return max node
     */
    public T max() {
        return maxHelper(root);
    }

    /**
     * Find the max using recursive function
     * @param node: recursive node
     * @return: return max node
     */
    private T maxHelper(GenTreeNode node) {
        if (node == null) {
            return null;
        } else if (node.rightNode == null) {
            return (T) node.data;
        } else {
            return maxHelper(node.rightNode);
        }
    }

    /**
     * find the min node in a Treen min data value
     * @return: return min node
     */
    public T min() {
        return minHelper(root);
    }

    /**
     * helper method to min
     * @param node: recursive
     * @return
     */
    private T minHelper(GenTreeNode node) {
        if (node == null) {
            return null;
        } else if (node.leftNode == null) {
            return (T) node.data;
        } else {
            return minHelper(node.leftNode);
        }
    }

    /**
     * remove a node by value
     * @param num: value to be removed
     */
    public void remove(T num) {
        removeHelper(root, num);
    }

    /**
     * Find the node, match the value, then remove it
     * @param node: recursive node
     * @param data: data to be removed
     */
    private void removeHelper(GenTreeNode node, T data) {
        if (node == null) {
            return;
        }
        //balance search tree, find which subtree value could be
        if (node.data.compareTo(data) == -1 && node.rightNode != null) {
            removeHelper(node.rightNode, data);
        } else if (node.data.compareTo(data) == 1 && node.leftNode != null) {
            removeHelper(node.leftNode, data);
        } else {//data matches
            if (node.leftNode == null && node.rightNode == null) {//leaf, just set to null
                GenTreeNode parentNode = node.parentNode;
                node.parentNode = null;
                if (parentNode.leftNode != null) {
                    parentNode.leftNode = null;
                    return;
                }
                if (parentNode.rightNode != null) {
                    parentNode.rightNode = null;
                    return;
                }
                return;
            } else if (node.leftNode == null) {//has right child
                node.data = (T) node.rightNode.data;
                node.rightNode = null;
                return;
            } else if (node.rightNode == null) {//has left child
                node.data = (T) node.leftNode.data;
                node.leftNode = null;
                return;
            } else {//has two nodes
                node.data = (T)minNode(node.rightNode).data;
                removeHelper(minNode(node.rightNode), (T) minNode(node.rightNode).data);//remove min again
                return;
            }
        }
    }

    /**
     * Return the min node, to work with remove method
     * @param node: recursive node
     * @return: min node
     */
    private GenTreeNode minNode(GenTreeNode node) {
        if (node == null) {
            return null;
        } else if (node.leftNode == null) {
            return node;
        } else {
            return minNode(node.leftNode);
        }
    }

    public static void main(String[] args) {

        System.out.println("Generic Tree Test Code:");
        System.out.println("Adding Students ...");

        Tree<Student> tree = new Tree<Student>();

        tree.InsertNode(new Student("Smith", "John", 10, 3.5));
        tree.InsertNode(new Student("Sparks", "Jane", 12, 4.5));
        tree.InsertNode(new Student("Duval", "Mike", 10, 3.0));
        tree.InsertNode(new Student("Huss", "Daniel", 10, 3.5));
        tree.InsertNode(new Student("Storm", "Julia", 9, 4.0));
        tree.InsertNode(new Student("Ness", "Eve", 13, 4.0));
        tree.InsertNode(new Student("Edson", "Thomas", 10, 4.0));

        System.out.println("\n\nTree preorder traversal:\n");
        tree.preorderTraversal();

        System.out.println("\n\nTree postorder traversal:\n");
        tree.postorderTraversal();

        System.out.println("\n\nTree inorder traversal:\n");
        tree.inorderTraversal();

        System.out.println("\n\nTesting tree's toString (uses an inorder traversal):");
        System.out.println(tree);

        // test the size method
        System.out.println("\n\nThe tree has " + tree.size() + " nodes.");

        System.out.println("\n\nTesting tree's reverse order traversal");
        tree.reverseorderTraversal();

        System.out.println("\n\nTree depth: " + tree.depth());

        System.out.println("\n\nThe Max is: " + tree.max());

        System.out.println("\n\nThe Min is: " + tree.min());

        System.out.println("----------------------\n");

        System.out.println("\n\nTree remove Jane Sparks:");
        tree.remove(new Student("Sparks", "Jane", 12, 4.5));

        System.out.println("\n\nTree preorder traversal:\n");
        tree.preorderTraversal();

        System.out.println("\n\nTree postorder traversal:\n");
        tree.postorderTraversal();

        System.out.println("\n\nTree inorder traversal:\n");
        tree.inorderTraversal();

        System.out.println("----------------------\n");

        System.out.println("\n\nTree remove Julia Storm:");
        tree.remove(new Student("Storm", "Julia", 9, 4.0));

        System.out.println("\n\nTree preorder traversal:\n");
        tree.preorderTraversal();

        System.out.println("\n\nTree postorder traversal:\n");
        tree.postorderTraversal();

        System.out.println("\n\nTree inorder traversal:\n");
        tree.inorderTraversal();



        System.out.println("Generic Tree2 Adding Strings ...");
        Tree<String> tree2 = new Tree<String>();

        tree2.InsertNode(new String("car"));
        tree2.InsertNode(new String("all"));
        tree2.InsertNode(new String("bike"));
        tree2.InsertNode(new String("dice"));
        tree2.InsertNode(new String("xdc"));

        System.out.println("\n\nGen. Tree2 with int. preorder traversal:\n");
        tree2.preorderTraversal();

        System.out.println("\n\nGen. Tree2 with int. postorder traversal:\n");
        tree2.postorderTraversal();

        System.out.println("\n\nGen. Tree2 with int. inorder traversal:\n");
        tree2.inorderTraversal();


        System.out.println("\n\nGeneric Tree3 Adding Integers ...");
        Tree<Integer> tree3 = new Tree<Integer>();

        tree3.InsertNode(new Integer(1));
        tree3.InsertNode(new Integer(2));
        tree3.InsertNode(new Integer(3));
        tree3.InsertNode(new Integer(4));
        tree3.InsertNode(new Integer(5));

        System.out.println("\nGen. tree3 with int. preorder traversal:\n");
        tree3.preorderTraversal();

        System.out.println("\n\nGen. tree3 with int. postorder traversal:\n");
        tree3.postorderTraversal();

        System.out.println("\n\nGen. tree3 with int. inorder traversal:\n");
        tree3.inorderTraversal();

    }
}
